//
// Created by 高森森 on 2022/2/17.
//

#ifndef LEETCODE_SOLUTION52_H
#define LEETCODE_SOLUTION52_H

#include <iostream>
#include <vector>
using namespace std;
#include<unordered_map>
#include<set>
#include <algorithm>
#include <map>
#include <stack>
#include <numeric>
class Solution52 {
    vector<vector<int>> G;
    stack<pair<int,int>> lasts[55];
    vector<int> res;
    void dfs(int node, int pre, int level, vector<int>& a) {
        int re = -1, lev = -1;
        for(int i = 1; i <= 50; ++i) {
            if(lasts[i].size() && lasts[i].top().first > lev && gcd(i, a[node]) == 1) {
                re = lasts[i].top().second;
                lev = lasts[i].top().first;
            }
        }
        res[node] = re;
        for(int ne : G[node]) {
            if(ne != pre) {
                lasts[a[node]].push({level, node});
                dfs(ne, node, level + 1, a);
                lasts[a[node]].pop();
            }
        }
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        G.resize(n);
        for(auto& e : edges) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        res.resize(n);
        dfs(0, -1, 0, nums);
        return res;
    }
    };


#endif //LEETCODE_SOLUTION52_H
